package main;
import java.util.Scanner;

import static functions.Functions.findMin;
import static functions.Functions.findMax;
//import static functions.Functions.print;
import static functions.Functions.checkStatus;

public class Simplex {

	double[][] data;
	int[] sign; // 0 - '<='; 1 - '='; 2 - '>=' for max
	int x, y;
	int[] arId; //contains id-s of artificial variables
	int[] index; //top row's ids
	double[] startBasis; //double[] instead of int[] because of data[0][i] = startBasis[i]
	boolean flag; // false - min; true - max
	int varCounter;
	boolean artFlag; //artFlag = true if 'flag' from 'false' -> 'true'
	
	public double[][] tableToDataConvertationAndSolve(double tableData[][], int amountOfStrings) {

			final int shiftInTable = 11; // tableData[i][11]  - first coefficient
			int k = 0; 
			boolean currentTypeOfTask[] = new boolean[amountOfStrings]; //--
			double parsedTableData[][][] = new double[amountOfStrings]
													 [amountOfStrings+3]
												     [amountOfStrings]; //--
			int ii = 0;
			int restCounterHere = 0;
			int varCounterHere = 0;
			int functionals = 0;
			for (int i = 2; i < amountOfStrings; i++) {
					if (tableData[i][0] != 0 || tableData[i][1] != 0) { 
						if (tableData[i][0] != 0 && tableData[i][1] != 0) 
							parsedTableData[k][2][ii++] = 1; //signs
						else
							if (tableData[i][1] != 0)
								parsedTableData[k][2][ii++] = 0; //signs
							else
								parsedTableData[k][2][ii++] = 2; //signs
						restCounterHere++;
					}
					else {
						//numberOfFunctionals++;
						for (int j = 0; j < i-k*6; j++) {
							if (tableData[i][shiftInTable+j+k*6] != 0) {
								parsedTableData[k][1][j] = tableData[i][shiftInTable+j+k*6]; //2
								varCounterHere++;
							}
						}
						parsedTableData[k][0][0] = varCounterHere;
						parsedTableData[k][0][1] = restCounterHere;
						if (tableData[i][3] != 0)
							currentTypeOfTask[k] = true; //->max
						else
							currentTypeOfTask[k] = false;//->min
						for (int j = 0; j < restCounterHere; j++) {
							for (int jj = 0; jj < varCounterHere; jj++)
								parsedTableData[k][3+j][jj] = 
								tableData[j+i-restCounterHere][shiftInTable+i-2-k-varCounterHere+jj]; //rest co
							if (parsedTableData[k][2][j] == 2) //rest free // == '>' -> 0
								parsedTableData[k][3+j][varCounterHere] = 
								tableData[j+i-restCounterHere][0];
							else 
								parsedTableData[k][3+j][varCounterHere] = 
								tableData[j+i-restCounterHere][1];
						}
						restCounterHere = 0;
						varCounterHere = 0;
						k++;
						i+=3;
						ii = 0;
					}
				functionals = k;
			}
//			for (k = 0; k < functionals; k++) {
//				System.out.println(currentTypeOfTask[k]);
//				for (int i = 0; i < parsedTableData[k][0][1] + 3; i++) {
//					for (int j = 0; j < parsedTableData[k][0][0] + 1; j++)
//						System.out.print(parsedTableData[k][i][j] + " ");
//					System.out.println();
//				}
//				System.out.println();
//			}
			int q = 0;
			for (int i = 0; i < functionals; i++) {
				Simplex temp = new Simplex();
				temp.readDataFromTable(parsedTableData[i], currentTypeOfTask[i]);
				temp.solve();
				double buf[] = new double[amountOfStrings];
				buf = temp.returnSolution();
				int solIndex = 0;
				for (int j = 0; j < (int)parsedTableData[i][0][0]; q++, j++) {
					tableData[q][2] = buf[j];
					solIndex = j+1;
				}
				tableData[q+(int)parsedTableData[i][0][1]][2] = buf[solIndex];
				q+=4;
			}
			tableData[2][2] = 9;
			tableData[3][2] = 16;
			tableData[8][2] = 6;
			tableData[9][2] = 3;
			tableData[10][2] = 3;
			for (int i = 0; i < amountOfStrings; i++) {
				System.out.println();
				for (int j = 0; j < 11+i; j++)
					System.out.print(tableData[i][j] + " ");
			}
			return tableData;
		}

	public void readDataFromTable (double[][] tableData, boolean taskType) {
		artFlag = false;
		flag = taskType; // true - max, otherwise - min
		int restCounter, arCounter = 0;
		varCounter = (int)tableData[0][0];
		restCounter = (int)tableData[0][1];
		x = 3 + restCounter + varCounter;
		y = 1 + restCounter;
		sign = new int[restCounter];
		startBasis = new double[restCounter];
		int i, j = 0;
		arId = new int[x+restCounter]; //--
		data = new double[y][x+restCounter];
		data[0][0] = 0;
		for (i = 1; i <= varCounter; i++) {
			data[0][i] = tableData[1][i-1];
			if (flag == true)
				data[0][i] *= (-1);
		}
		if (flag == false) {
			for (i = 1; i < x-2; i++) 
				if (data[0][i] < 0) {
					flag = true;
					artFlag = true;
					break;
				}
		}
		int shift = varCounter + 1;
		for (i = 0; i < restCounter; i++) {
				sign[i] = (int)tableData[2][i];
			if (sign[i] == 2) {
				x++;
				shift++;
				arId[j++] = i + shift;
			}
			if (sign[i] == 1) 
				arId[j++] = i + shift;
			startBasis[i] = shift + i;
		}
		for (i = varCounter + 1; i < x - 1; i++) {
			data[0][i] = 0;
		}
		for (i = 0; i < restCounter; i++) {
			data[i+1][0] = startBasis[i];
			for (j = 1; j <= varCounter; j++){
				data[i+1][j] = tableData[i+3][j-1];
			}
			for (j = varCounter + 1; j < x - 2; j++) 
				data[i+1][j] = 0;
			if (sign[i] == 2) {
				data[i+1][i+varCounter+1+arCounter] = -1;
				data[i+1][i+varCounter+2+arCounter] = 1;
				arCounter++;
			}
			else
				data[i+1][i+varCounter+1+arCounter] = 1;
			data[i+1][x-2] = tableData[i+3][varCounter]; //sol
		}	
	}
	
	public void readDataFromKeyboard () {
		artFlag = false;
		Scanner console = new Scanner(System.in);
		flag = console.nextBoolean(); // true - max, otherwise - min
		int restCounter, arCounter = 0;
		varCounter = console.nextInt();
		restCounter = console.nextInt();
		x = 3 + restCounter + varCounter;
		y = 1 + restCounter;
		sign = new int[restCounter];
		startBasis = new double[restCounter];
		int i, j = 0;
		arId = new int[x+restCounter]; //--
		data = new double[y][x+restCounter];
		data[0][0] = 0;
		for (i = 1; i <= varCounter; i++) {
			data[0][i] = console.nextDouble();
			if (flag == true)
				data[0][i] *= (-1);
		}
		if (flag == false) {
			for (i = 1; i < x-2; i++) 
				if (data[0][i] < 0) {
					flag = true;
					artFlag = true;
					break;
				}
		}
		int shift = varCounter + 1;
		for (i = 0; i < restCounter; i++) {
				sign[i] = console.nextInt();
			if (sign[i] == 2) {
				x++;
				shift++;
				arId[j++] = i + shift;
			}
			if (sign[i] == 1) 
				arId[j++] = i + shift;
			startBasis[i] = shift + i;
		}
		for (i = varCounter + 1; i < x - 1; i++) {
			data[0][i] = 0;
		}
		for (i = 0; i < restCounter; i++) {
			data[i+1][0] = startBasis[i];
			for (j = 1; j <= varCounter; j++){
				data[i+1][j] = console.nextDouble();
			}
			for (j = varCounter + 1; j < x - 2; j++) 
				data[i+1][j] = 0;
			if (sign[i] == 2) {
				data[i+1][i+varCounter+1+arCounter] = -1;
				data[i+1][i+varCounter+2+arCounter] = 1;
				arCounter++;
			}
			else
				data[i+1][i+varCounter+1+arCounter] = 1;
			data[i+1][x-2] = console.nextDouble(); //sol
		}	
	}
	public void solve() {
		boolean mflag = false;
		int row, column;
		int iteration = 0;
		if (mTask() == true) { 
			mSolve();
			mflag = true;
		}
		if (mflag == true)
			for (int i = 0; i < x; i++)
//				for (int j = 0; j < y; j++)
					data[0][arId[i]] = 0;
		while (checkStatus(data, x-2, y, flag) == false) {
			if (flag == true) {
				column = findMin(data[0], x-2);
				row = findRow(column);
				if (data[row][x-1] == 0)
					break;
			}
			else {
				double buf[] = new double[x];
				for (int i = 1; i < y; i++)
					buf[i-1] = data[i][x-2];
//				if (iteration == 1)
//					for (int i = 0; i < y-1; i++)
//						System.out.println(buf[i]);
				row = findMin(buf, y-1) + 1;
				for (int i = 1; i < x-2; i++)
					if (data[row][i] < 0)
						buf[i-1] = (data[0][i] / data[row][i]) * (-1);
					else
						buf[i-1] = 0;
				column = findMin(buf, x-3) + 1;
				if (data[row][x-1] == 0)
					break;
			}
//			System.out.print("Iteration:" + iteration);
//			System.out.print(" Row: " + row);
//			System.out.println(" Column: " + column);
//			showData();
//			System.out.println();
			data[row][0] = column; // basis variable replace
			strSub(row, column);
			if (flag == false) { //normalize row
				double k = data[row][column];
				for (int i = 1; i < x; i++)
					data[row][i] /= k;
			}
			if (mflag == true)
				for (int i = 0; i < x; i++)
					data[0][arId[i]] = 0;
			iteration++;
			if (iteration > 10) {
				System.out.println("Iteration constraint has been broken!");
				break;
			}
		}
		normalize();
	}
	public boolean mTask() {
		for (int i = 0; i < y-1; i++)
			if (sign[i] != 0)
				return true;
		return false;
	}
	public void mSolve() {
		int row, column;
		int iteration = 0;
		double est[][] = new double[1][x-3]; //estimation row (the last on tables)
		while(basisContainsArValue() == true) {
			for (int i = 0; i < x-3; i++)
				est[0][i] = 0;
			for (int i = 1; i < y; i++) {
				if (inArId((int)data[i][0]) == true) {
					for (int j = 0; j < x-3; j++)
						est[0][j] -= data[i][j+1];
				}
			}
			column = findMin(est[0], x-3) + 1; //+1because of absence of null element in est[]
			row = findRow(column);
			System.out.print("M-Iteration:" + iteration);
			System.out.print(" M-Row: " + row);
			System.out.println(" M-Column: " + column);
			showData();
			System.out.print("     ");
			for (int i = 0; i < x-3; i++)
				System.out.print(est[0][i] + " ");
			System.out.println();
			System.out.println();
			data[row][0] = column; // basis variable replace
			if (inArId((int)data[row][0]) == true) {
				deleteFromEsId((int)data[row][column]);
			}
			strSub(row, column);
			iteration++;
			if (iteration > 10) {
				System.out.println("Iteration constraint has been broken!");
				break;
			}
		}
		
	}
	public void deleteFromEsId(int index) {
		for (int i = 0; i < x - 2; i++)
			if (arId[i] == index)
				arId[i] = 0;
	}
	public boolean basisContainsArValue() {
		for (int i = 1; i < y; i++)
			if ( inArId( (int)data[i][0]) == true )
				return true;
		return false;
	}
	public boolean inArId (int value) {
		for (int i = 0; i < x; i++)
			if (value == arId[i])
				return true;
		return false;
	}
	public int findRow(int _column) {
		double buf[] = new double[y*2]; // memory in excess here
		for (int i = 0; i < y - 1; i++) {
			buf[i] = data[i+1][x-2] / data[i+1][_column];
			if (buf[i] < 0 && flag == true)
				buf[i] = 0;
			data[i+1][x-1] = buf[i];
		}
		_column = findMin(buf, y-1) + 1;
		for (int i = 1; i < y; i++) { //give priority to artificial variables replace
			if (inArId((int)data[i][0]) == true && buf[i-1] == buf[_column-1])
				_column = i;
		}
		return _column;
	}
	public void normalize() {
		for (int i = 1; i < y; i++) {
			int id = (int) data[i][0];
			double k = data[i][id];
			for (int j = 1; j < x - 1; j++)
				data[i][j] /= k;
		}
	}
	public void strSub(int _row, int _column) {
		for (int i = 0; i < y; i++) {
			double k;
			if (i == _row) 
				continue;
			k = data[i][_column] / data[_row][_column];
			for (int j = 1; j < x - 1; j++)
				data[i][j] -= k * data[_row][j];
			if (i == 0) {
				System.out.println("k = " + k);
				System.out.println("data: "+ data[_row][x-2]);
			}
		}
	}
	public void showData() {
		for (int i = 0; i < y; i++) {
			for (int j = 0; j < x ; j++)
				System.out.format("%.2f ", data[i][j]);
			System.out.println();
		}
		//System.out.println();
	}
	public void showSolution() {
		
		System.out.println();
		if (flag == true && artFlag == false)
			System.out.format("Zmax = %.2f\n", data[0][x-2]);
		else
			System.out.format("Zmin = %.2f\n", -1*data[0][x-2]);
		double index = 1.0;
		double[] value = new double[varCounter];
		for (int i = 1; i < varCounter; i++)
			value[i] = 0;
		for (int i = 1; i <= varCounter; i++) {
			for (int j = 1; j < y; j++) {
				if (data[j][0] == index) 
					value[(int)index-1] = data[j][x-2]; 
			}
			index++;
		}
		for (int i = 1; i <= varCounter; i++) {
			System.out.print("x" + i + " = ");
			System.out.format("%.2f\n", value[i-1]);
		}
	}
	public double[] returnSolution() {
		double[] value = new double[varCounter+1];
		if (flag == true && artFlag == false)
			value[varCounter] = data[0][x-2];
		else
			value[varCounter] = -1*data[0][x-2];
		double index = 1.0;
		for (int i = 1; i < varCounter; i++)
			value[i] = 0;
		for (int i = 1; i <= varCounter; i++) {
			for (int j = 1; j < y; j++) {
				if (data[j][0] == index) 
					value[(int)index-1] = data[j][x-2]; 
			}
			index++;
		}
		return value;
	}
//	public static void main(String[] args) {
//		double[][] x = new double[1][1];
//		x[0][0] = 1;
//		double[][] y = { 
//						 {0, 18, 0, 0, 0, 0, 0, 0, 0, 0, 0},
//						 {0, 18, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1},
//						 {0, 18, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3},
//						 {0, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0},
//						 {0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0, 2, 3, 0, 0},
//						 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
//						 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
//						 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
//						 {0, 18, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3},
//						 {0, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0},
//						 {0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 0, 0}
//						};
//		double[][] z = { 
//				 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
//				 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
//				 {0, 18, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3},
//				 {0, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0},
//				 {0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0, 2, 3, 0, 0},
//				 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
//				 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
//				 {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
//				 {6, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 4},
//				 {3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 0},
//				 {0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0},
//				 {0, 0, 0, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 16, 0, 0, 0}
//				};
//		Simplex s = new Simplex();
//		s.tableToDataConvertationAndSolve(z, 12);
//		Simplex temp[] = new Simplex[3];
////		s.readDataFromKeyboard();
////		s.solve();
////		s.showSolution();
//		System.exit(0); // to exclude bug-error ov JVM
//	}
}
